package com.ggqq.sort;

import java.util.Arrays;

public class GuiBing {
    public static void main(String[] args) {
        //归并排序

        //原始待排序数组
        int[] arr = {3,44,38,5,47,15,36,26,27,3,46,4,19,50,48,-8,101000};

        //我们先给一个左右两边是有序的一个数组，先来进行归并操作
        //int[] arr1 = {4,5,7,8,1,2,3,6};

        //----------------拆分----------------
        chaiFen(arr,0,arr.length-1);

        //----------------归并----------------
        guiBing(arr,0,arr.length/2,arr.length-1);



        //遍历原数组
        System.out.println(Arrays.toString(arr));
    }

    private static void chaiFen(int[] arr, int startIndex, int endIndex) {
        //计算中间索引
        int centerIndex = (startIndex+endIndex)/2;
        if(startIndex<endIndex){
            chaiFen(arr,startIndex,centerIndex);//左边拆分
            chaiFen(arr,centerIndex+1,endIndex);//右边拆分
            guiBing(arr,startIndex,centerIndex,endIndex);
        }
    }

    private static void guiBing(int[] arr1, int startIndex, int centerIndex, int endIndex) {
        //定义一个临时数组
        int[] tempArr  = new int[endIndex-startIndex+1];
        //定义左边数组的起始索引
        int i= startIndex;
        //定义右边数组的起始索引
        int j= centerIndex+1;
        //定义临时数组的起始索引
        int index = 0;
        //比较左右两个数组的元素大小，往临时数组中放
        while(i<=centerIndex && j<=endIndex){
            if(arr1[i]<=arr1[j]){
                tempArr[index]=arr1[i];
                i++;
            }else {
                tempArr[index] = arr1[j];
                j++;
            }
            index++;
        }
        //处理可能剩余的元素(左边剩余)
        while(i<=centerIndex){
            tempArr[index]=arr1[i];
            i++;
            index++;
        }
        //处理可能剩余的元素(右边剩余)
        while(j<=endIndex){
            tempArr[index] = arr1[j];
            j++;
            index++;
        }

        //将临时数组中的元素取到原数组中
        for (int k = 0; k < tempArr.length; k++) {
            arr1[k+startIndex]=tempArr[k];
        }

    }

}